\documentclass[revision]{FPSAC2017}

\articlenumber{21}
\addbibresource{21_Danilov_Karzanov.bib}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{coro}[thm]{Corollary}

\crefname{thm}{Theorem}{Theorems}

\newcommand{\Xcomment}[1]{}

\usepackage{amstext,amscd}

\newenvironment{numitem}{\refstepcounter{equation}\begin{enumerate}%
\item[(\thesection.\arabic{equation})]$\quad$}{\end{enumerate}}
 %
\newenvironment{numitem1}{\refstepcounter{equation}\begin{enumerate}%
\item[(\thesection.\arabic{equation})]}{\end{enumerate}}

\newcommand{\refeq}[1]{(\ref{eq:#1})}  % reference to equation

\def\rest#1{_{\,\vrule height 1.6ex width 0.05em depth 0pt\, #1}}

\newcommand{\SEC}[1]{\ref{sec:#1}}  % reference to section
\newcommand{\SSEC}[1]{\ref{ssec:#1}}  % reference to subsection

\def\Rset{{\mathbb R}}
\def\Kset{{\mathbb K}}
\def\Qset{{\mathbb Q}}
\def\Zset{{\mathbb Z}}

\def\Ascr{{\cal A}}
\def\Bscr{{\cal B}}
\def\Cscr{{\cal C}}
\def\Dscr{{\cal D}}
\def\Escr{{\cal E}}
\def\Fscr{{\cal F}}
\def\Gscr{{\cal G}}
\def\Iscr{{\cal I}}
\def\Kscr{{\cal K}}
\def\Lscr{{\cal L}}
\def\Mscr{{\cal M}}
\def\Oscr{{\cal O}}
\def\Pscr{{\cal P}}
\def\Qscr{{\cal Q}}
\def\Rscr{{\cal R}}
\def\Sscr{{\cal S}}
\def\Tscr{{\cal T}}
\def\Wscr{{\cal W}}
\def\Xscr{{\cal X}}
\def\Yscr{{\cal Y}}

\def\frakF{{\mathfrak F}}
\def\frakL{{\mathfrak L}}
\def\frakR{{\mathfrak R}}
\def\frakS{{\mathfrak S}}

\def\tilde{\widetilde}
\def\hat{\widehat}
\def\bar{\overline}
\def\eps{\epsilon}

\def\Path{{\rm Path}}
\def\Sign{{\rm sign}}

\def\bfC{{\bf C}}
\def\bfM{{\bf M}}

\def\Iw{{I^\circ}}
\def\Jw{{J^\circ}}
\def\Ib{{I^\bullet}}
\def\Jb{{J^\bullet}}
\def\Kw{{K^\circ}}
\def\Lw{{L^\circ}}
\def\Kb{{K^\bullet}}
\def\Lb{{L^\bullet}}

\def\Yr{{Y^{\rm r}}}
\def\Yc{{Y^{\rm c}}}
\def\Xr{{X^{\rm r}}}
\def\Xc{{X^{\rm c}}}
\def\Mr{{M^{\rm r}}}
\def\Mc{{M^{\rm c}}}
\def\Mrc{{M^{\rm rc}}}

%--------------



\title[Minors of quantum matrices]{On universal quadratic identities for minors of quantum matrices}

\author[V.~Danilov and A.~Karzanov]{Vladimir~I.~Danilov\thanks{\href{mailto:danilov@cemi.rssi.ru}{danilov@cemi.rssi.ru}}\addressmark{1}
\and Alexander~V.~Karzanov\thanks{\href{mailto:sasha@cs.isa.ru}{sasha@cs.isa.ru}, \href{mailto:akarzanov7@gmail.com}{akarzanov7@gmail.com} (corresponding author)}\addressmark{2}}

\address{\addressmark{1}Central Inst.~of Economics and Mathematics of
RAS, 47, Nakhimovskii Prosp., 117418 Moscow, Russia\\
\addressmark{2}Inst.~for System Analysis at FRC
Computer Science and Control of RAS, 9, Prosp. 60 Let Oktyabrya, 117312 Moscow,
Russia}

\received{November 11, 2016} \revised{\today}

\abstract{We give a complete combinatorial characterization of homogeneous
quadratic identities of ``universal character'' valid for minors of quantum
matrices over a field. This is obtained as a consequence of a study of
quantized minors of the so-called \emph{path matrices} associated with certain
planar graphs generalizing Cauchon graphs.}

\keywords{quantum matrix, $q$-minor, Cauchon diagram, planar graph, path
matrix}

\begin{document}

\maketitle


%----------------------- Sec. 1

\section{Introduction}  \label{sec:intr}

The idea of quantization has proved its importance to bridge commutative and
noncommutative versions of certain algebraic structures and promote better
understanding various aspects of the latter versions. One popular structure is
the \emph{quantized coordinate ring} $\Rscr=\Oscr_q(\mathfrak{M}_{m,n}(\Kset))$
of $m\times n$ matrices over a field $\Kset$, where $q$ is a nonzero element of
$\Kset$, usually called the \emph{algebra of $m\times n$ quantum matrices}.
Here $\Rscr$ is generated by entries (indeterminates) of an $m\times n$ matrix
$X$ subject to Manin's relations~\cite{man}: for $i<\ell\le m$ and $j<k\le n$,
   %
   \begin{gather}
   x_{ij}x_{ik}=qx_{ik}x_{ij},\qquad x_{ij}x_{\ell j}=qx_{\ell j}x_{ij},
                                              \label{eqn:xijkl}\\
   x_{ik}x_{\ell j}=x_{ \ell j}x_{ik}\quad \mbox{and}\quad
    x_{ij}x_{\ell k}-x_{\ell k}x_{ij}=(q-q^{-1})x_{ik}x_{\ell j}.  \nonumber
    \end{gather}
    %

We study quadratic identities for minors of quantum matrices, or \emph{quantum
minors}. For a discussion on aspects and applications of such identities, see
e.g.,~\cite{fio,KL,LR,LZ,TT} (where the list is incomplete). We present a
novel, and rather transparent, combinatorial method which enables us to
completely characterize and efficiently verify homogeneous quadratic identities
of universal character that are valid for quantum minors. The identities of our
interest can be written as
  %
  \begin{equation} \label{eqn:q_ident}
  \sum(\Sign_i q^{\delta_i} [I_i|J_i]_q\, [I'_i|J'_i]_q \colon i=1,\ldots,N)=0,
  \end{equation}
  %
where $\delta_i\in\Zset$, ~$\Sign_i\in\{+,-\}$, and $[I|J]_q$ denotes the
quantum minor whose rows and columns are indexed by $I\subseteq[m]$ and
$J\subseteq[n]$, respectively. (Hereinafter, for a positive integer $n'$, we
write $[n']$ for $\{1,2,\ldots,n'\}$.) The homogeneity means that each of the
sets $I_i\cup I'_i,\, I_i\cap I'_i,\, J_i\cup J'_i,\, J_i\cap J'_i$ is
invariant of $i$, and the term ``universal'' means that~\eqref{eqn:q_ident}
should be valid independently of $\Kset,q$ and a $q$-matrix (a matrix whose
entries obey Manin's relations and, possibly, additional ones). Note that any
cortege $(I|J,I'|J')$ may be repeated in~\eqref{eqn:q_ident} many times.

Our approach has two sources. The first one is the \emph{flow-matching} method
elaborated in~\cite{DKK} to characterize quadratic identities for usual minors
(viz. for $q=1$). In that case the identities are viewed as
 %
  \begin{equation} \label{eqn:com_ident}
  \sum(\Sign_i[I_i|J_i]\, [I'_i|J'_i] \colon i=1,\ldots,N)=0.
  \end{equation}
  %
In the method of~\cite{DKK}, each cortege $S=(I|J,I'|J')$ determines a certain
set $\Mscr(S)$ of so-called \emph{feasible matchings}. The main theorem
in~\cite{DKK} asserts that~\eqref{eqn:com_ident} is valid (universally) if and
only if the families $\Iscr^+$ and $\Iscr^-$ of corteges $S_i$ with $\Sign_i=+$
and $\Sign_i=-$, respectively, are \emph{balanced}, in the sense that the total
families of feasible matchings for corteges occurring in $\Iscr^+$ and in
$\Iscr^-$ are equal.

The second source is the path method due to Casteels~\cite{cast1,cast2}. He
associated with each Cauchon diagram $C$ of size $m\times n$ (see~\cite{cauch})
a certain directed planar graph $G=G_C$ with $m+n$ distinguished vertices
$r_1,\ldots,r_m,c_1,\ldots,c_n$, and considered the $m\times n$ \emph{path
matrix} $P_G=(p_{ij})$ of $G$. This matrix possesses three important
properties. (i) It is a $q$-matrix, and therefore, $x_{ij}\mapsto p_{ij}$ gives
a homomorphism of $\Rscr$ to the corresponding algebra generated by the
$p_{ij}$. (ii) It admits an analog of Lindstr\"om's Lemma~\cite{lind}: for any
$I\subseteq [m]$ and $J\subseteq[n]$ with $|I|=|J|$, the minor $[I|J]_q$ of
$P_G$ can be expressed via systems of \emph{disjoint paths} from $\{r_i\colon
i\in I\}$ to $\{c_j\colon j\in J\}$ in $G$. (iii) Using Cauchon's
Algorithm~\cite{cauch} interpreted in graph terms in~\cite{cast1,cast2}, one
shows that if the diagram $C$ is maximal (i.e., has no black cells), then
$\Path_G$ becomes a \emph{generic $q$-matrix} (see Corollary~3.2.5
in~\cite{cast2}).

In this work we consider a more general class of planar graphs, called
\emph{SE-graphs}; they possess the above properties~(i),(ii) as well. Our goal
is to characterize quadratic identities just for the class of path matrices of
SE-graphs. Since this class contains a generic $q$-matrix, the identities are
automatically valid in $\Rscr$. As a result, we obtain necessary and sufficient
conditions for the quantum version (in \cref{tm:nec_q_bal,tm:suff_q_bal}), namely:~\eqref{eqn:q_ident} is valid (universally) if
and only if the families of corteges $\Iscr^+$ and $\Iscr^-$ along with the
function $\delta$ are $q$-\emph{balanced}, which now means the existence of a
bijection between the families of feasible matchings for $\Iscr^+$ and
$\Iscr^-$ that is agreeable with $\delta$ in a certain sense. Note also that
our method of establishing or verifying one or another universal identity
admits a rather transparent implementation.

The paper is organized as follows. Section~2 contains basic definitions and
statements. Section~3 describes important ingredients and tools in our method:
\emph{double flows} (pairs of path systems related to corteges $(I|J,I'|J')$),
\emph{feasible matchings}, and transformations of double flows by use of
\emph{exchange operations}. The crucial working tool exhibited here is
\cref{cor:gen_exch} which follows from a result on exchange operations
proved in~\cite{DK} (stated in \cref{tm:single_exch}). Based on these,
Section~4 outlines a proof of the sufficiency: \eqref{eqn:q_ident} is valid if
the corresponding $\Iscr^+,\Iscr^-,\delta$ are $q$-balanced
(\cref{tm:suff_q_bal}). Also Section~4 contains an algorithm of
recognizing the $q$-balancedness and one illustration and finishes with
\cref{tm:nec_q_bal} (without a proof) concerning the necessity of the
$q$-balancedness.

For proofs in detail, additional results and numerous applications, see the
full version posted in arXiv:\href{https://arxiv.org/abs/1604.00338}{1604.00338[math.QA]}.

%----------------------- Sec. 2

\section{Basic definitions and statements}  \label{sec:prelim}

\noindent\textbf{Paths in graphs.} Throughout, by a \emph{graph} we mean a
directed graph. A \emph{path} in a graph $G=(V,E)$ is a sequence
$P=(v_0,e_1,v_1,\ldots,e_k,v_k)$ such that each $e_i$ is an edge connecting the
vertices $v_{i-1},v_i$. An edge $e_i$ is called \emph{forward} if it is
directed from $v_{i-1}$ to $v_i$, denoted as $e_i=(v_{i-1},v_i)$, and \emph{
backward} otherwise (when $e_i=(v_i,v_{i-1})$). The path $P$ is called {\em
directed} if it has no backward edge, and {\em simple} if all vertices $v_i$
are different. When $k>0$ and $v_0=v_k$, ~$P$ is called a \emph{cycle}, and
called a \emph{simple cycle} if, in addition, $v_1,\ldots,v_k$ are different.
  \medskip

\noindent\textbf{SE-graphs.} A graph $G=(V,E)$ of this sort (also denoted as
$(V,E;R,C)$) satisfies the following conditions:
 \smallskip

(SE1) $G$ is planar (with a fixed layout in the plane);

(SE2) $G$ has edges of two types: \emph{horizontal} edges, or \emph{H-edges},
which are directed to the right, and \emph{vertical} edges, or \emph{V-edges},
which are directed downwards (so each edge points to either \emph{south} or
\emph{east}, justifying the term ``SE-graph'');

(SE3) $G$ has two distinguished subsets of vertices: set $R=\{r_1,\ldots,r_m\}$
of \emph{sources} and set $C=\{c_1,\ldots,c_n\}$ of \emph{sinks}; moreover,
$r_1,\ldots,r_m$ are disposed on a vertical line, in this order upwards, and
$c_1,\ldots,c_n$ are disposed on a horizontal line, in this order from left to
right; each vertex of $G$ belongs to a directed path from $R$ to $C$.
  \smallskip

We denote by $W=W_G$ the set $V-(R\cup C)$ if \emph{inner} vertices of $G$. We
also say that $G$ is an $(m,n)$ \emph{SE-graph} (where $m:=|R|$ and $n:=|C|$).
An example is drawn in \cref{fig:SE}.
  \medskip

\begin{figure}[htb]
\begin{center}
\includegraphics[scale=0.7]{qr1}
\end{center}
\vspace{-0.5cm}
 \caption{An SE-graph with $m=3$ and $n=4$}
 \label{fig:SE}
  \end{figure}

\noindent\emph{Remark 1.} A representative special case is formed by the
SE-graphs equivalent to \emph{Cauchon graphs} introduced in~\cite{cast1} (which
are associated with Cauchon diagrams~\cite{cauch}). In this case,
$R=\{(0,i)\colon i\in[m]\}$, $C=\{(j,0)\colon j\in[n]\}$, and $W\subseteq
[n]\times [m]$. When $W=[n]\times [m]$, we refer to such a graph as the
\emph{extended $(m,n)$-grid} and denote by $\Gamma_{m,n}$.
  \medskip

Each inner vertex $v\in W$ of an SE-graph $G$ is regarded as a
\emph{generator}. We assign the weight $w(e)$ to each edge $e=(u,v)\in E$ in a
way similar to that for Cauchon graphs in~\cite{cast1}, namely:
  \smallskip

  (W1) $w(e):=v$ if $e$ is an H-edge with $u\in R$;

  (W2) $w(e):=u^{-1}v$ if $e$ is an H-edge and $u,v\in W$;

  (W3) $w(e):=1$ if $e$ is a V-edge.

 \smallskip
This gives rise to defining the weight $w(P)$ of a directed path
$P=(v_0,e_1,v_1,\ldots, e_k,v_k)$ to be the ordered (from left to right)
product, namely:
  %
  \begin{equation} \label{eqn:wPe}
  w(P):=w(e_1)w(e_2)\cdots w(e_k).
  \end{equation}

The generators $W$ are assumed to be subject to (quasi)commutation laws, which
match those for Cauchon graphs in~\cite{cast1}. More precisely, for distinct
$u,v\in W$,
  \smallskip

  (G1) if there is a directed \emph{horizontal} path from $u$ to $v$ in $G$, then $uv=qvu$;

  (G2) if there is a directed \emph{vertical} path from $u$ to $v$ in $G$, then
$vu=quv$;

  (G3) otherwise $uv=vu$.
  \medskip

\noindent\textbf{Quantum minors.}  It is convenient for us to visualize
matrices in the Cartesian form: for an $m\times n$ matrix $A=(a_{ij})$, the row
indices $i=1,\ldots,m$ are assumed to increase upwards, and the column indices
$j=1,\ldots,n$ from left to right.

We denote by $A(I|J)$ the submatrix of $A$ whose rows and columns are indexed
by $I\subseteq[m]$ and $J\subseteq[n]$, respectively. Let $|I|=|J|=:k$, and let
$I$ consist of $i_1<\cdots<i_k$, and $J$ consist of $j_1<\cdots<j_k$. Then the
$q$-\emph{determinant} of $A(I|J)$, or the $q$-\emph{minor} of $A$ for $(I|J)$,
is defined as
  %
  \begin{equation} \label{eqn:qminor}
  [I|J]_{A,q}:=\sum\nolimits_{\sigma\in S_k} (-q)^{\ell(\sigma)}
    \prod\nolimits_{d=1}^{k} a_{i_dj_{\sigma(d)}},
    \end{equation}
    %
where the product under $\prod$ is ordered by increasing $d$, and
$\ell(\sigma)$ denotes the \emph{length} (number of inversions) of a
permutation $\sigma$. The terms $A$ and/or $q$ in $[I|J]_{A,q}$ may be omitted
when they are clear from the context.
  \medskip

\noindent\textbf{Path matrix.} An important construction in~\cite{cast1}
associates with a Cauchon graph $G$ a certain matrix, called the path matrix of
$G$. This is extended to an arbitrary $(m,n)$ SE-graph $G=(V,E)$, namely: the
\emph{path matrix} $\Path=\Path_G$ of $G$ is meant to be the $m\times n$ matrix
whose entries are defined by
  %
  \begin{equation} \label{eqn:Mat}
  \Path(i|j):=\sum\nolimits_{P\in\Phi_G(i|j)} w(P), \qquad (i,j)\in [m]\times [n],
  \end{equation}
  %
where $\Phi_G(i|j)$ is the set of directed paths from $r_i$ to $c_j$ in $G$. In
particular, $\Path(i|j)=0$ if $\Phi_G(i|j)=\emptyset$. Thus, the entries of
$\Path_G$ belong to the $\Kset$-algebra $\Lscr_G$ of Laurent polynomials
generated by the set $W$ of inner vertices of $G$ subject to~(G1)--(G3).
  \medskip

\noindent\textbf{Flows.} Let $\Escr^{m,n}$ be the set of pairs $(I|J)$ with
$I\subseteq [m]$, $J\subseteq [n]$ and $|I|=|J|$. Borrowing terminology
from~\cite{DKK}, for $(I|J)\in\Escr^{m,n}$, a set $\phi$ of pairwise disjoint
directed paths from the source set $R_I:=\{r_i\colon i\in I\}$ to the sink set
$C_J:=\{c_j\colon j\in J\}$ in $G$ is called an $(I|J)$-\emph{flow}.

The set of $(I|J)$-flows $\phi$ in $G$ is denoted by $\Phi(I|J)=\Phi_G(I|J)$.
We assume that the paths forming $\phi$ are ordered by increasing the source
indices: if $I$ consists of $i(1)<i(2)<\cdots< i(k)$ and $J$ consists of
$j(1)<j(2)<\cdots<j(k)$, then $\ell$-th path $P_\ell$ in $\phi$ begins at
$r_{i(\ell)}$, and therefore, $P_\ell$ ends at $c_{j(\ell)}$ (which follows
from the planarity of $G$, the ordering of sources and sinks in the boundary of
$G$ and the fact that the paths in $\phi$ are disjoint). We write
$\phi=(P_1,P_2,\ldots,P_k)$ and (similar to path systems in~\cite{cast1})
define the weight of $\phi$ to be the ordered product
  %
  \begin{equation} \label{eqn:w_phi}
  w(\phi):=w(P_1)w(P_2)\cdots w(P_k).
  \end{equation}

Generalizing a $q$-analog of Lindstr\"om's Lemma shown for Cauchon graphs
in~\cite{cast1}, one can express minors of path matrices via flows as follows.
  %
  \begin{thm}[\cite{DK}] \label{tm:Linds}
Let $G$ be an $(m,n)$ SE-graph. Then for the path matrix $\Path=\Path_G$ and
for any $(I|J)\in \Escr^{m,n}$, there holds
  %
  \begin{equation} \label{eqn:Lind}
[I|J]_{\Path,q}=\sum\nolimits_{\phi\in\Phi(I|J)} w(\phi).
  \end{equation}
  \end{thm}

An important fact is that the (quasi)commutation relations for the entries of
$\Path_G$ are similar to those for the canonical generators $x_{ij}$ of the
quantum algebra $\Rscr$ in~\eqref{eqn:xijkl}.
  %
  \begin{prop} \label{pr:Path-A}
~For an SE-graph $G$, the entries of its path matrix $\Path_G$ satisfy Manin's
relations.
 \end{prop}

\noindent (A proof, omitted here, can be given as an easy application of our
flow-matching method.) This implies that the map $x_{ij}\mapsto \Path_G(i|j)$
determines a homomorphism of $\Rscr$ to the subalgebra of $\Lscr_G$ generated
by the entries of $\Path_G$, i.e., $\Path_G$ is a $q$-matrix for any SE-graph
$G$. A sharper property holds for the graph associated with the $m\times n$
Cauchon diagram without black cells. Namely, Corollary~3.2.5 in~\cite{cast2}
relying on Cauchon's Algorithm~\cite{cauch} gives the following property (in
our terms).
  %
  \begin{thm}  \label{tm:Cach-Cast}
Let $G$ be the extended grid $\Gamma_{m,n}$ (defined in Remark~1). Then
$\Path_G$ is a generic $q$-matrix, i.e., $x_{ij}\mapsto \Path_G(i|j)$ gives an
injective map of $\Rscr$ to $\Lscr_G$.
\end{thm}

Due to this property, the universal quadratic relations that we establish for
minors of path matrices of SE-graphs turn out to be automatically valid for the
algebra $\Rscr$ of quantum matrices, and vice versa.

%----------------------- Sec. 3

\section{Double flows, matchings, and exchange operations}  \label{sec:double}

Quadratic identities of our interest involve products of the form
$[I|J]_q[I'|J']_q$, where $(I|J),$ $(I'|J')\in \Escr^{m,n}$. This leads us to a
study of pairs of flows $\phi\in \Phi(I|J)$ and $\phi'\in \Phi(I'|J')$. We need
some definitions and conventions, borrowing terminology from~\cite{DKK}.

Given $I,J,I',J',\phi,\phi'$ as above, we call the pair $(\phi,\phi')$ a
\emph{double flow} in $G$. Let
   %
   \begin{gather}
   \Iw:=I-I',\quad \Jw:=J-J',\quad \Ib:=I'-I,\quad \Jb:=J'-J,
                          \label{eqn:white-black} \\
   \Yr:=\Iw\cup\Ib\quad \mbox{and}\quad \Yc:=\Jw\cup\Jb. \nonumber
   \end{gather}

\noindent Then $|I|=|J|$ and $|I'|=|J'|$ imply that $|\Iw|-|\Ib|=|\Jw|-|\Jb|$
and that $|\Yr|+|\Yc|$ is even. As before, we refer to the quadruple
$(I|J,I'|J')$ as a \emph{cortege}, and call $(\Iw,\Ib,\Jw,\Jb)$ the
\emph{refinement} of $(I|J,I'|J')$, or a \emph{refined cortege}.

We interpret $\Iw$ and $\Ib$ as the sets of \emph{white} and \emph{black}
elements of $\Yr$, respectively, and similarly for $\Jw,\Jb,\Yc$, and visualize
these objects by use of a \emph{circular diagram} in which the elements of
$\Yr$ (respectively $\Yc$) are disposed in the increasing order from left to right in
the upper (respectively lower) half of a circumference $O$. For example, if
$\Iw=\{3\}$, $\Ib=\{1,4\}$, $\Jw=\{2',5'\}$ and $\Jb=\{3',6',8'\}$, then the
diagram is viewed as in the left fragment of the picture below. (Here, to avoid
a mess, we denote the elements of $\Yc$ with primes.)

\vspace{0cm}
\begin{center}
\includegraphics[scale=0.8]{qr3}
\end{center}
\vspace{-0.3cm}

\noindent\textbf{Matchings.} ~A partition $M$ of $\Yr\sqcup \Yc$ into 2-element
sets is called a \emph{perfect matching} on $\Yr\sqcup \Yc$ (where $\sqcup$
stands for the disjoint union). We say that $\pi\in M$ is: an $R$-\emph{couple}
if $\pi\subseteq \Yr$, a $C$-\emph{couple} if $\pi\subseteq \Yc$, and an
$RC$-\emph{couple} if $|\pi\cap \Yr|=|\pi\cap \Yc|=1$ (as though $\pi$
``connects'' two sources, two sinks, and one source and one sink,
respectively). A perfect matching $M$ is called a \emph{feasible} matching for
$(\Iw,\Ib,\Jw,\Jb)$ (and for $(I|J,I'|J')$) if:
 \smallskip

(FM1) ~for each $\pi=\{i,j\}\in M$, the elements $i,j$ have different colors if
$\pi$ is an $R$- or $C$-couple, and have the same color if $\pi$ is an
$RC$-couple; and

(FM2) ~$M$ is \emph{planar}, in the sense that the chords connecting the
couples in the circumference $O$ are pairwise non-intersecting.
 \smallskip
 
\begingroup\emergencystretch=.3em
The set of feasible matchings for $(\Iw,\Ib,\Jw,\Jb)$ is denoted by
$\Mscr_{\Iw,\Ib,\Jw,\Jb}$, or $\Mscr(I|J,I'|J')$. One can show that this set is
nonempty whenever $\Yr\sqcup\Yc\ne\emptyset$. The right fragment of the above
picture illustrates an instance of feasible matchings.
\endgroup
 \smallskip

Next we return to a double flow $(\phi,\phi')$ as above, and our aim is to
associate to it a feasible matching for $(\Iw,\Ib,\Jw,\Jb)$. Let $V_\phi$ and
$E_\phi$ denote the sets of vertices and edges of $G$ occurring in $\phi$,
respectively; and similarly for $\phi'$. Consider the subgraph $\langle
U\rangle$ of $G$ induced by the set of edges
   $$
   U:=E_\phi\triangle E_{\phi'},
   $$
(where $A\triangle B$ denotes the symmetric difference $(A-B)\cup (B-A)$ of
sets $A,B$). Then a vertex $v$ of $\langle U\rangle$ has degree 1 if $v\in
R_{\Iw}\cup R_{\Ib}\cup C_{\Jw}\cup C_{\Jb}$, and degree 2 or 4 otherwise. We
modify $\langle U\rangle$ by splitting each vertex $v$ of degree 4 in $\langle
U\rangle$ into two vertices $v',v''$ disposed in a small neighborhood of $v$ so
that the edges entering (respectively leaving) $v$ become entering $v'$ (respectively leaving
$v''$):

\vspace{0cm}
\begin{center}
\includegraphics[scale=0.8]{qr4}
\end{center}
\vspace{-0.2cm}

The resulting graph, denoted as $\langle U\rangle '$, is planar and has
vertices of degree only 1 and 2. Therefore, $\langle U\rangle'$ consists of
pairwise disjoint (non-directed) simple paths $P'_1,\ldots,P'_k$ and, possibly,
simple cycles $Q'_1,\ldots,Q'_d$. The corresponding images of
$P'_1,\ldots,P'_k$ (respectively $Q'_1,\ldots,Q'_d$) give paths $P_1,\ldots,P_k$
(respectively cycles $Q_1,\ldots,Q_d$) in $\langle U\rangle$. When $\langle U\rangle$
has vertices of degree 4, some of the latter paths and cycles may be
self-intersecting and may ``touch'', but not ``cross'', each other. It is not
difficult to see the following
  %
  \begin{lem} \label{lm:P1Pk}
{\rm (i)} $k=(|\Iw|+|\Ib|+|\Jw|+|\Jb|)/2$;

{\rm(ii)} the set of endvertices of $P_1,\ldots,P_k$ is $R_{\Iw\cup\Ib}\cup
C_{\Jw\cup\Jb}$; moreover, each $P_i$ connects either $R_{\Iw}$ and $R_{\Ib}$,
or $C_{\Jw}$ and $C_{\Jb}$, or $R_{\Iw}$ and $C_{\Jw}$, or $R_{\Ib}$ and
$C_{\Jb}$;

{\rm(iii)} in each path $P_i$, the edges of $\phi$ and the edges of $\phi'$
have different directions (say, the former edges are all forward, and the
latter ones are all backward).
  \end{lem}

Thus, each $P_i$ is representable as a concatenation $P_i^{(1)}\circ
P_i^{(2)}\circ\ldots\circ P_i^{(\ell)}$ of forwardly and backwardly directed
paths which are alternately contained in $\phi$ and $\phi'$, called the
\emph{segments} of $P_i$. We say that $P_i$ is an \emph{exchange path}. The
endvertices of $P_i$ determine a pair of elements of $\Yr\sqcup \Yc$, denoted
by $\pi_i$. Then $M:=\{\pi_1,\ldots,\pi_k\}$ is a perfect matching on
$\Yr\sqcup \Yc$. Moreover, it is feasible, since~(FM1) follows from
\cref{lm:P1Pk}(ii), and~(FM2) from the fact that $P'_1,\ldots,P'_k$ are
disjoint simple paths in $\langle U\rangle'$. We denote $M$ as $M(\phi,\phi')$,
and for $\pi\in M$, denote the exchange path $P_i$ corresponding to $\pi$ by
$P(\pi)$.

\begin{coro} \label{cor:Mphiphip}
$M(\phi,\phi')\in\Mscr_{\Iw,\Ib,\Jw,\Jb}$.
  \end{coro}

\noindent \textbf{Flow exchange operation.} It rearranges a given double flow
$(\phi,\phi')$ for $(I|J,\,I'|J')$ into another double flow $(\psi,\psi')$ for
some $(\tilde I|\tilde J,\,\tilde I'|\tilde J')$, as follows. Fix a submatching
$\varPi\subseteq M(\phi,\phi')$, and combine the exchange paths related to
$\varPi$, forming the set of edges
   $$
   \Escr:= \cup (E_{P(\pi)}\colon \pi\in\varPi).
   $$
 %
(where $E_{P(\pi)}$ is the edge set of $P(\pi)$). Using \cref{lm:P1Pk},
one can show the following
 %
  \begin{lem} \label{lm:phi-psi}
Let $V_{\varPi}:=\cup(\pi\in\varPi)$. Define
  $$
  \tilde I:=I\triangle (V_{\varPi}\cap \Yr),\;\; \tilde I':=I'\triangle (V_{\varPi}\cap\Yr), \;\;
  \tilde J:=J\triangle (V_{\varPi}\cap \Yc),\;\; \tilde J':=J'\triangle (V_{\varPi} \cap\Yc).
  $$
Then the subgraph $\psi$ induced by $E_\phi\triangle\Escr$ gives a $(\tilde
I|\tilde J)$-flow, and the subgraph $\psi'$ induced by $E_{\phi'}\triangle
\Escr$ gives a $(\tilde I'|\tilde J')$-flow in $G$. Furthermore, $E_\psi\cup
E_{\psi'}= E_\phi\cup E_{\phi'}$,\; $E_\psi\triangle E_{\psi'}= E_\phi\triangle
E_{\phi'}$ ($=U$), and $M(\psi,\psi')=M(\phi,\phi')$.
  \end{lem}
  %

We call the transformation $(\phi,\phi')\stackrel{\varPi}\longmapsto
(\psi,\psi')$ in this lemma the \emph{flow exchange operation} for
$(\phi,\phi')$ \emph{using} $\varPi\subseteq M(\phi,\phi')$. Clearly the
exchange operation applied to $(\psi,\psi')$ using the same $\varPi$ returns
$(\phi,\phi')$.

So far our description has been close to that given for the commutative case
in~\cite{DKK}. From now on we will essentially deal with the quantum version.
The next theorem serves the main working tool in our arguments; its proof,
based on a bulk of combinatorics on paths and flows, is given in~\cite{DK}.
  %
  \begin{thm} \label{tm:single_exch}
Let $\phi$ be an $(I|J)$-flow, and $\phi'$ an $(I'|J')$-flow in $G$. Let
$(\psi,\psi')$ be the double flow obtained from $(\phi,\phi')$ by the flow
exchange operation using a single couple $\pi=\{i,j\}\in M(\phi,\phi')$. Then:

{\rm(i)} when $\pi$ is an $R$- or $C$-couple and $i<j$,
   %
   \begin{eqnarray*}
   w(\phi)w(\phi')=qw(\psi)w(\psi') \quad &\mbox{in case}&\;\; i\in I\cup J; \\
 w(\phi)w(\phi')=q^{-1}w(\psi)w(\psi') \quad &\mbox{in case}&\;\;
                                                   i\in I'\cup J';
   \end{eqnarray*}

{\rm(ii)} when $\pi$ is an $RC$-couple, $w(\phi)w(\phi')=w(\psi)w(\psi')$.
  \end{thm}
  %

An immediate consequence from this theorem is the following.
  %
  \begin{coro} \label{cor:gen_exch}
For an $(I|J)$-flow $\phi$ and an $(I'|J')$-flow $\phi'$, let $(\psi,\psi')$ be
obtained from $(\phi,\phi')$ by the flow exchange operation using a set
$\varPi\subseteq M(\phi,\phi')$. Then
  %
  \begin{equation} \label{eqn:gen_exch}
   w(\phi)w(\phi')=q^{\zeta^\circ-\zeta^\bullet} w(\psi)w(\psi'),
   \end{equation}
   %
where $\zeta^\circ=\zeta^\circ(I|J,I'|J';\varPi)$ (respectively
$\zeta^\bullet=\zeta^\bullet(I|J,I'|J';\varPi)$) is the amount of $R$- or
$C$-couples $\pi=\{i,j\}\in \varPi$ such that $i<j$ and $i\in I\cup J$ (respectively
$i\in I'\cup J'$).
  \end{coro}
  %
Indeed, the flow exchange operation using the whole $\varPi$ reduces to
performing, step by step, the exchange operations using single couples $\pi\in
\varPi$ (taking into account that for any current double flow $(\eta,\eta')$
occurring in the process, the sets $E_\eta\cup E_{\eta'}$ and $E_\eta\triangle
E_{\eta'}$, as well as the matching $M(\eta,\eta')$, do not change; cf.
\cref{lm:phi-psi}). Then~\eqref{eqn:gen_exch} follows from
\cref{tm:single_exch}.

%----------------------- Sec. 4

\section{Quadratic identities and the $q$-balancedness}  \label{sec:q_relat}

As before, we consider an $(m,n)$ SE-graph $G=(V,E;R,C)$ and deal with
$q$-minors $[I|J]=[I|J]_{\Path,q}$ of its path matrix $\Path=\Path_G$. In this
section, based on \cref{cor:gen_exch} and developing a quantum version
of the flow-matching method elaborated for the commutative case in~\cite{DKK},
we establish sufficient conditions of a general form on quadratic relations for
$q$-minors to be valid independently of $G$ and some other data (mentioned in
Remark~2 below), referring to them as ``universal quadratic identities''.

Relations that we deal with are of the form
  %
  \begin{equation} \label{eqn:gen_QR}
  \sum\nolimits_\Iscr q^{\alpha(I|J,I'|J')} [I|J][I'|J'] =
     \sum\nolimits_\Kscr q^{\beta(K|L,K'|L')} [K|L][K'|L'],
     \end{equation}
     %
where $\alpha, \beta$ are integer-valued, $\Iscr$ is a family of corteges
$(I|J,I'|J')\in \Escr^{m,n}\times \Escr^{m,n}$ (with possible multiplicities),
and similarly for $\Kscr$. (Then~\eqref{eqn:gen_QR} is equivalent
to~\eqref{eqn:q_ident} with $\delta$ corresponding to $(\alpha,\beta)$.) We
assume that $\Iscr$ and $\Kscr$ are \emph{homogeneous}, in the sense that for
any $(I|J,I'|J')\in\Iscr$ and $(K|L,K'|L')\in\Kscr$,
   %
   \begin{equation} \label{eqn:homogen}
I\cup I'=K\cup K',\quad J\cup J'=L\cup L',\quad I\cap I'= K\cap K',\quad J\cap
J'=L\cap L'.
  \end{equation}
 %
Moreover, we shall see that only the refinements $(\Iw,\Ib,\Jw,\Jb)$ and
$(\Kw,\Kb,\Lw,\Lb)$ are important, whereas the sets $I\cap I'$ and $J\cap J'$
are, in fact, indifferent.

To formulate our validity criterion, we need some definitions and notation.

$\bullet$ A tuple $(I|J,I'|J';M)$, where $(I|J,I'|J')\in \Iscr$ and
$M\in\Mscr_{\Iw,\Ib,\Jw,\Jb}$ (cf.~(FM1)--(FM2)), is called a
\emph{configuration} for $\Iscr$. The family of all configurations for $\Iscr$
is denoted by $\bfC(\Iscr)$. Similarly, we define the family $\bfC(\Kscr)$ of
configurations for $\Kscr$.

$\bullet$ Define $\bfM(\Iscr)$ to be the family of all matchings $M$ (with
possible multiplicities) occurring in the members of $\bfC(\Iscr)$. Define
$\bfM(\Kscr)$ in a similar way.

$\bullet$ Families $\Iscr$ and $\Kscr$ are called \emph{balanced} (borrowing
terminology from~\cite{DKK}) if there exists a bijection
$(I|J,I'|J';M)\stackrel{\gamma}\longmapsto (K|K',L|L';M')$ between
$\bfC(\Iscr)$ and $\bfC(\Kscr)$ such that $M=M'$. In other words, $\Iscr$ and
$\Kscr$ are balanced if $\bfM(\Iscr)=\bfM(\Kscr)$.

$\bullet$ Families $\Iscr$ and $\Kscr$ along with functions
$\alpha:\Iscr\to\Zset$ and $\beta:\Kscr\to\Zset$ are called $q$-\emph{balanced}
if there exists a bijection $\gamma$ as above such that, for each
$(I|J,I'|J';M)\in\bfC(\Iscr)$ and for $(K|K',L|L';M)=\gamma(I|J,I'|J';M)$,
there holds
  %
  \begin{equation} \label{eqn:q_balan}
  \beta(K|K',L|L')-\alpha(I|J,I'|J')=\zeta^\circ-
                            \zeta^\bullet.
  \end{equation}
  %
(In particular, $\Iscr,\Kscr$ are balanced.) Here $\zeta^\circ,\zeta^\bullet$
are defined according to \cref{cor:gen_exch}. Namely,
$\zeta^\circ=\zeta^\circ(I|J,I'|J';\varPi)$ and
$\zeta^\bullet=\zeta^\bullet(I|J,I'|J';\varPi)$, where $\varPi$ is the set of
couples $\pi\in M$ such that the colorings of $\pi$ in the refined corteges
$(\Iw,\Ib,\Jw,\Jb)$ and $(\Kw,\Kb,\Lw,\Lb)$ are different. (Then $\zeta^\circ$
($\zeta^\bullet$) is the number of $R$- and $C$-couples $\{i,j\}\in\varPi$ with
$i<j$ and $i\in \Iw\cup\Jw$ (respectively $i\in \Ib\cup\Jb)$.) We say that
$(\Kw,\Kb,\Lw,\Lb)$ is obtained from $(\Iw,\Ib,\Jw,\Jb)$ by the \emph{index
exchange operation} using $\varPi$.

  \begin{thm} \label{tm:suff_q_bal}
Let $\Iscr$ and $\Kscr$ be homogeneous families on
$\Escr^{m,n}\times\Escr^{m,n}$, and let $\alpha:\Iscr\to\Zset$ and
$\beta:\Kscr\to\Zset$. Suppose that $\Iscr,\Kscr,\alpha,\beta$ are
$q$-balanced. Then~\eqref{eqn:gen_QR} is valid for $q$-minors of the path
matrix of any $(m,n)$ SE-graph $G=(V,E;R,C)$.
  \end{thm}
    %
  \begin{proof}
~We fix $G$ and denote by $\Dscr(I|J,I'|J')$ the set of double flows for
$(I|J,I'|J') \in\Iscr\cup\Kscr$ in $G$. A summand concerning
$(I|J,J'|J')\in\Iscr$ in the left side of~\eqref{eqn:gen_QR} can be expressed via
double flows as follows, ignoring the factor of $q^{\alpha(\cdot)}$:
  %
  \begin{multline} \label{eqn:ff}
  [I|J][I'|J']   =\left( \sum\nolimits_{\phi\in\Phi_G(I|J)} w(\phi)\right)
     \times\left(\sum\nolimits_{\phi'\in\Phi_G(I'|J')} w(\phi')\right) \\
  =\sum\nolimits_{(\phi,\phi')\in\Dscr(I|J,I'|J')} w(\phi)w(\phi')
                       \qquad\qquad\qquad\qquad\qquad\qquad                  \\
  =\sum\nolimits_{M\in\Mscr_{\Iw,\Ib,\Jw,\Jb}}
  \sum\nolimits_{(\phi,\phi')\in\Dscr(I|J,I'|J')\,:\, M(\phi,\phi')=M} w(\phi)w(\phi').
   \qquad
  \end{multline}

The summand for $(K|L,K'|L')\in\Kscr$ in the right side of~\eqref{eqn:gen_QR} is
expressed similarly.

Consider a configuration $S=(I|J,I'|J';M)\in\bfC(\Iscr)$ and suppose that
$(\phi,\phi')$ is a double flow for $(I|J,I'|J')$ with $M(\phi,\phi')=M$ (if
such a double flow in $G$ exists). Since $\Iscr,\Kscr,\alpha,\beta$ are
$q$-balanced, $S$ is bijective to some configuration
$S'=(K|L,K'|L';M)\in\bfC(\Kscr)$ satisfying~\eqref{eqn:q_balan}. As explained
earlier, the cortege $(K|L,K'|L')$ is obtained from $(I|J,I'|J')$ by the index
exchange operation using some $\varPi\subseteq M$. Then the flow exchange
operation applied to $(\phi,\phi')$ using this $\varPi$ results in a double
flow $(\psi,\psi')$ for $(K|L,K'|L')$ which satisfies
relation~\eqref{eqn:gen_exch} in \cref{cor:gen_exch}.
Comparing~\eqref{eqn:gen_exch} with~\eqref{eqn:q_balan}, we observe that
  %
  $$
  q^{\alpha(I|J,I'|J')} w(\phi)w(\phi')= q^{\beta(K|K',L|L')} w(\psi)w(\psi').
  $$
Furthermore, such a map $(\phi,\phi')\mapsto(\psi,\psi')$ gives a bijection
between all double flows concerning configurations in $\bfC(\Iscr)$ and those
in $\bfC(\Kscr)$. Now the desired equality~\eqref{eqn:gen_QR} follows by
considering the last term in expression~\eqref{eqn:ff} and the corresponding
term in the analogous expression concerning $\Kscr$.
 \end{proof}

As a consequence of \cref{tm:Cach-Cast,tm:suff_q_bal}, the
following result is obtained.
  %
  \begin{coro} \label{cor:QR_quant_matr}
If $\Iscr,\Kscr,\alpha,\beta$ as above are $q$-balanced, then
relation~\eqref{eqn:gen_QR} is valid for the corresponding minors in the
algebra $\Rscr$ of quantum $m\times n$ matrices.
  \end{coro}

\noindent\emph{Remark 2.} When speaking of a \emph{universal quadratic
identity} of the form~\eqref{eqn:gen_QR} with homogeneous $\Iscr$ and $\Kscr$,
abbreviated as a \emph{UQ identity}, we mean that it depends neither on the
SE-graph $G$ nor on the field $\Kset$ and element $q\in \Kset^\ast$, and that
the index sets can be modified as follows. Given $(I|J,I'|J')\in\Iscr$, let
$A:=I\triangle I'$, $B:=J\triangle J'$, $S:=I\cap I'$ and $T:=J\cap J'$
Take arbitrary $\tilde m\ge |A|$ and $\tilde n\ge |B|$, disjoint sets $\tilde
A,\tilde S\subseteq [\tilde m]$, and disjoint sets $\tilde B,\tilde T\subseteq
[\tilde n]$ with $|\tilde A|=|A|$, $|\tilde B|=|B|$, $|\tilde S|-|\tilde
T|=|S|-|T|$. Let $\lambda:A\to \tilde A$ and $\mu:B\to\tilde B$ be the order
preserving maps. Transform each $(I|J,I'|J')\in \Iscr$ into $(\tilde I|\tilde
J, \tilde I'|\tilde J')$, obtaining a new family $\tilde \Iscr$ on
$\Escr^{\tilde m,\tilde n}\times \Escr^{\tilde m,\tilde n}$, where
   $$
   \tilde I:=\tilde S \cup \lambda(I-S), \quad \tilde I':=\tilde S \cup\lambda(I'-S),
   \quad \tilde J:=\tilde T \cup \mu(J-T), \quad \tilde J':=\tilde T
   \cup\mu(J'-T).
   $$
Turn $\Kscr$ into $\tilde K$ in a similar way. One can see that if
$\Iscr,\Kscr,\alpha,\beta$ are $q$-balanced, then so are $\tilde \Iscr,\tilde
\Kscr$, keeping $\alpha,\beta$. Therefore, if~\eqref{eqn:gen_QR} is valid for
$\Iscr,\Kscr$, then it is valid for $\tilde \Iscr,\tilde\Kscr$ as well.
 \medskip

One can say that identity~\eqref{eqn:gen_QR}, where all summands have positive
signs, is written in the canonical form. Sometimes, however, it is more
convenient to consider equivalent identities having negative summands in one or
both sides (e.g., of the form~\eqref{eqn:q_ident}).
  \medskip

We can suggest a rather simple algorithm which has as the input a corresponding
quadruple $\Iscr,\Kscr,\alpha,\beta$ and recognizes the $q$-balanced for it.
Therefore, in light of \cref{tm:suff_q_bal,tm:nec_q_bal}, the
algorithm decides whether or not the given quadruple determines a UQ identity
of the form~\eqref{eqn:gen_QR}.
 \smallskip

\noindent\textbf{Algorithm.} Compute the set $\Mscr_{\Iw,\Ib,\Jw,\Jb}$ of
feasible matchings $M$ for each $(I|J,I'|J')\in\Iscr$, and similarly for
$\Kscr$. For each instance $M$ occurring there, extract the family
$\bfC_M(\Iscr)$ of all configurations concerning $M$ in $\bfC(\Iscr)$, and
extract a similar family $\bfC_M(\Kscr)$ in $\bfC(\Kscr)$. If
$|\bfC_M(\Iscr)|\ne |\bfC_M(\Kscr)|$ for at least one instance $M$, then
$\Iscr$ and $\Kscr$ are not balanced at all. Otherwise for each $M$, we seek
for a required bijection $\gamma_M: \bfC_M(\Iscr)\to \bfC_M(\Kscr)$ by solving
the maximum matching problem in the corresponding bipartite graph $H_M$. More
precisely, the vertices of $H_M$ are the tuples $(I|J,I'|J';M)$ and
$(K|L,K'|L';M)$ occurring in $\bfC_M(\Iscr)$ and $\bfC_M(\Kscr)$, and such
tuples are connected by edge in $H_M$ if they obey~\eqref{eqn:q_balan}. Find a
maximum matching $N$ in $H_M$. If $|N|=|\bfC_M(\Iscr)|$, then $N$ determines
the desired $\gamma_M$ in a natural way. Taking together, these $\gamma_M$ give
a bijection between $\bfC(\Iscr)$ and $\bfC(\Kscr)$ as required, implying that
$\Iscr,\Kscr,\alpha,\beta$ are $q$-balanced. And if $|N|<|\bfC_M(\Iscr)|$ for
at least one instance $M$, then the algorithm declares the
non-$q$-balancedness.
  \medskip

\noindent\textbf{Example.} ~Next we illustrate our method with one example.
Recall that sets $I,J\subseteq[n]$ are called \emph{weakly separated} if, up to
renaming $I$ and $J$, there holds $(\ast)$: $|I|\ge |J|$, and $J-I$ has a
partition $\{J_1,J_2\}$ such that $J_1<I-J<J_2$ (where we write $X<Y$ if $x<y$
for any $x\in X$ and $y\in Y$). Let $k:=|I|$ and $\ell:=|J|$. Leclerc and
Zelevinsky~\cite{LZ} proved that: \emph{two quantum flag minors
$[I]:=[[k]|I]_q$ and $[J]:=[[\ell]|J]_q$ \emph{quasicommute}, i.e., satisfy
$[I][J] = q^c [J][I]$ for some $c\in\Zset$, if and only if $I$ and $J$ are
weakly separated. Moreover, assuming~$(\ast)$, $c$ is equal to $|J_2|-|J_1|$.}
One can show ``if'' part of this theorem as follows. (For ``only if'' part, a
characterization of quasicommuting non-flag minors, and many other applications
of our method, see arXiv:\href{https://arxiv.org/abs/1604.00338}{1604.00338[math.QA]}.)

Let $A:=[k]-[\ell]$. Assuming~$(\ast)$, one can see that
$\Mscr([k]|I,[\ell]|J)$ has exactly one feasible matching $M$; namely, $J_1$ is
coupled with the first $|J_1|$ elements of $I-J$, ~$J_2$ is coupled with the
last $|J_2|$ elements of $I-J$ (forming all $C$-couples), and the rest of $I-J$
is coupled with $A$ (forming all $RC$-couples). Observe that the index exchange
operation applied to the cortege $([k]|I,[\ell]|J)$ using the whole $M$ swaps
$([k]|I)$ and $([\ell]|J)$ (as it changes the colors of all elements of
$(I-J)\cup(J-I)\cup A$). Also the set of $C$-couples of $M$ consist of $|J_1|$
couples $\{i,j\}$ with $i<j$ and $i\in J_1$, and $|J_2|$ couples $\{i,j\}$ with
$i<j$ and $j\in J_2$. This gives $\zeta^\circ=|J_2|$ and $\zeta^\bullet=|J_1|$.
Hence the (one-element) families $\Iscr=\{([k]|I,[\ell]|J)\}$ and
$\Kscr=\{([\ell]|J,[k]|I)\}$ along with $\alpha(([k]|I,[\ell]|J))=0$ and
$\beta(([\ell]|J,[k]|I))=|J_2|-|J_1|$ are $q$-balanced. Now ``if'' part (with
$c=|J_2|-|J_1|$) follows from \cref{tm:suff_q_bal}.
 \medskip

Finally, we formulate (without a proof) a converse assertion to
\cref{tm:suff_q_bal}, saying that the $q$-balancedness condition is
necessary as well. This gives a complete characterization for the UQ identities
on quantum minors.

\begin{thm} \label{tm:nec_q_bal}
Let $\Kset$ be a field of characteristic zero and let $q\in\Kset^\ast$ be
transcendental over $\Qset$. Suppose that $\Iscr,\Kscr,\alpha,\beta$ (as in
\cref{sec:q_relat}) are not $q$-balanced. Then there exists, and can be
explicitly constructed, an SE-graph $G$ for which relation~\eqref{eqn:gen_QR}
is violated.
 \end{thm}

\printbibliography
\end{document}
